Search for: All records

In 1979, Hylland and Zeckhauser [26] gave a simple and general mechanism for a 6 one-sided matching market, given cardinal utilities of agents over goods. They use the power of a 7 pricing mechanism, which endows their mechanism with several desirable properties – it produces an 8 allocation that is Pareto optimal and envy-free, and the mechanism is incentive compatible in the 9 large. It therefore provides an attractive, off-the-shelf method for running an application involving 10 such a market. With matching markets becoming ever more prevalent and impactful, it is imperative 11 to characterize the computational complexity of this mechanism. 12 We present the following results: 13 1. A combinatorial, strongly polynomial time algorithm for the dichotomous case, i.e., 0/1 14 utilities, and more generally, when each agent’s utilities come from a bi-valued set. 15 2. An example that has only irrational equilibria; hence this problem is not in PPAD. 16 3. A proof of membership of the problem in the class FIXP; as a corollary we get that an 17 HZ equilibrium can always be expressed via algebraic numbers. For this purpose, we give 18 a new proof of the existence of an HZ equilibrium using Brouwer’s fixed point theorem; 19 the proof of Hylland and Zeckhauser used Kakutani’s fixed point theorem, which is more 20 involved. 21 4. A proof of membership of the problem of computing an approximate HZ equilibrium in the 22 class PPAD. 

We study the problem of finding a Tarski fixed point over the k-dimensional grid [n]^k. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point.